/*
    XTU OJ: 1331
    by: fifth_light
*/

#define MIN(a, b) ((a) > (b) ? (b) : (a))
#define MAX(a, b) ((a) > (b) ? (a) : (b))

#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>

int64_t bits[45][4];

void once(int len) {
    if (len == 1) {
        // 长度为1
        for (int i = 0; i < 4; i++) {
            bits[len - 1][i] = 1;
        }
    } else {
        // 从上次的推导
        once(len - 1);
        for (int i = 1; i <= 4; i++) {
            int min = MAX(i - 2, 1);
            int max = MIN(i + 2, 4);
            int64_t sum = 0;
            for (int j = min; j <= max; j++) {
                if (j != i) {
                    sum += bits[len - 2][j - 1];
                }
            }
            bits[len - 1][i - 1] = sum;
        }
    }
}

void prepare_table() {
    once(45);
    /*for (int i = 0; i < 45; i++) {
        for (int j = 0; j < 4; j++) {
            printf("%" PRId64 " ", bits[i][j]);
        }
        putchar('\n');
    }*/
}

int main(void) {
    prepare_table();
    int t;
    scanf("%d", &t);
    for(int i = 0; i < t; i++) {
        int n;
        scanf("%d", &n);
        int64_t sum = 0;
        for (int i = 0; i < 4; i++) {
            sum += bits[n - 1][i];
        }
        printf("%" PRId64 "\n", sum);
    }
    return 0;
}
